/**
 * 400. 第N个数字
 * https://leetcode-cn.com/problems/nth-digit/
 */
public class Solutions_400 {
    public static void main(String[] args) {
//        int n = 3;  // output: 3
//        int n = 11;  // output: 0
//        int n = 12;  // output: 1
//        int n = 210;  // output: 6
//        int n = 365;  // output: 158，5
//        int n = 1000;  // output: 3

//        int result = findNthDigit(n);
//        System.out.print(result + " ");

//        for (int i = 1; i <= 1000; i++) {
        for (int i = 1000; i <= 1000; i++) {
            int result = findNthDigit(i);
            System.out.print(result + " ");
        }
    }

    /**
     * 找规律：
     * 1. 根据 n 定位到所在的区间，即 [0, 9]，[10, 99]，[100, 999]，每个区间的数字位数是一致的
     * arr[0] = 9：表示数值 1 位时，共有 9 位数字，数字区间：[1, 9]
     * arr[1] = 189：表示数值 2 位时，共有 9 + (2 * 90) = 189 位数字，数字区间：[10, 99]
     * arr[2] = 2889：表示数值 3 位时，共有 189 + (3 * 900) = 2889 位数字，数字区间：[100, 999]
     * arr[3] = 38889：表示数值 4 位时，共有 2889 + (4 * 9000) = 38889 位数字，数字区间：[1000, 9999]
     * ...
     * 以 n = 1000 为例：
     * 1. 找到是在几位数的区间中
     *    1.1  1000 > 9，那么一定在二位数中，n - (1 * 9) = 991
     *    1.2  991 > 90，那么一定在三位数中，n - (2 * 90) = 811
     *    1.3  811 < 2700，那么 n = 1000 的所在的数，一定是一个三位数
     * 2. 定位到数字
     *    2.1  三位数的开始数字是：100
     *    2.2  那么在区间中，是在第 811 / 3 = 270 位
     *    2.3  计算得到 n = 1000 的所在数字：100 + 270 = 370
     * 3. 定位到数位
     *    3.1  取余数：811 % 3 = 1
     *    3.2  根据规律，知道余数为 1，即是左起第 1 个数位
     * 注意：
     *    例：n = 11 时，定位到数字 11，但是结果是 10 的尾数 0
     *    根据规律，余数为 0 时，结果为计算得到的所在数字的前一位数的尾数
     *
     *                   10 11 12 13 14 15 16 17 18 19 20 21 22 23
     * 1 2 3 4 5 6 7 8 9 1  0  1  1  1  2  1  3  1  4  1  5  1  6
     */
    public static int findNthDigit(int n) {
        long num = n;
        // size：数位数量，count：数位数量为 size 的数字个数
        long size = 1, count = 9;
        while (num > 0) {
            if (num > count * size) {
                // num 缩小，确定 num 是几位数
                num -= size * count;
                size ++;
                count *= 10;
            } else {
                // 第 n 位数在 [Math.pow(10, size - 1), Math.pow(10, size) - 1] 区间中产生
                long cnt = num / size;
                long left = num % size;
                // 区间的起始数字
                long start = (long) Math.pow(10, size - 1);
                // 第 n 位所在的数字
                long cur = start + cnt;
                if (left == 0) {
                    // cur 前一位数的尾数
                    return (int) ((cur - 1) % 10);
                } else {
                    // 有余数，那么余数，就是当前数字 start + count 的左起第 left 位
                    // 转化为字符串形式再取字符
//                    String str = String.valueOf(start + cnt);
//                    return str.charAt((int) left - 1) - '0';

                    // 数学计算方式，通过 left 计算除数，最后取余数
                    return (int) ((cur) / Math.pow(10, size - left)) % 10;
                }
            }
        }
        return -1;
    }
}
